'''
设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
[要求]
set和get方法的时间复杂度为O(1)
某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案
operators: [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],
k: 3
'''
class Solution:
    def LRU(self , operators , k ):
        # write code here
        lruDict = {}
        lruList = []
        result = []
        def set(key, val):
            # 更新列表+添加元素
            if key in lruList:
                lruList.remove(key)
            lruList.append(key)
            # 记录 key value
            lruDict[key] = val
            # 0 表示最不常用
            if len(lruList) > k:
                lruDict.pop(lruList.pop(0))
        def get(key):
            # 直接查找x,没有返回-1
            # 循环调用
            result.append(lruDict.get(key,-1))
            # 更新列表
            if key in lruList:
                lruList.remove(key)
                lruList.append(key)
        for i in operators:
            if len(i)==3:
                set(i[1],i[2])
            else:
                get(i[1])
        return result























